# Logical calculi and proofs.
(unit 9, unit 14) Complete the given proofs.
(105, 106, 107)
六、請完成下列演算，作答時需連同題目寫在答案卷上。（20%) (Please complete the following proofs. Notice: you should copy the whole questions on your answer sheet.)
(105)
(a)
$$
\lnot P \to P , (P \lor \lnot Q) \to R \vdash P\land R
$$
答.
![[basic-logic/---attachments/logic-problem-6-2025-11-15-20-49-05.svg]]
(b)
$$
(\forall x)(Px \lor \lnot Rx), (\exists x)Px \to (\forall x)(\lnot Qx \lor Rx), (\exists x)(Px \lor Rx) \vdash (\forall x)(Qx \to Px)
$$
答.
$$
\array{
1. & (∀x)(Px \lor ¬Rx) & \text{Pr} \\
2. & (∃x)Px → (∀x)(¬Qx \lor Rx) & \text{Pr} \\
3. & (∃x)(Px \lor Rx) & \text{Pr} \\
4. & Pa \lor Ra & \text{3, EI} \\
5. & Pa \lor ¬Ra & \text{1, UI} \\
6. & Ra ∨ Pa & \text{4, Comm} \\
7. & ¬¬Ra ∨ Pa & \text{6, DN} \\
8. & ¬Ra → Pa & \text{7, Imp} \\
9. & ¬¬Pa v ¬Ra & \text{5, DN} \\
10. & ¬Pa → ¬Ra & \text{9, Imp} \\
11. & ¬Pa → Pa & \text{10, 8, HS} \\
12. & ¬¬Pa ∨ Pa & \text{11, Imp} \\
13. & Pa ∨ Pa & \text{12, DN} \\
14. & Pa & \text{13, Dup} \\
15. & (∃x)Px & \text{14, EG} \\
16. & (∀x)(¬Qx ∨ Rx) & \text{2, 15, MP} \\
17. & ¬Qb ∨ Rb & \text{16, UI} \\
18. & Qb → Rb & \text{17, Imp} \\
19. & Pb ∨ ¬Rb & \text{1, UI} \\
20. & ¬Rb ∨ Pb & \text{19, Comm} \\
21. & Rb → Pb & \text{20, Imp} \\
22. & Qb → Pb & \text{18, 21, HS} \\
23. & (∀x)(Qx → Px) & \text{22, UG}
}
$$
---
六、請完成下列演算，作答時需連同題目寫在答案卷上。(30%) (Please complete the following proofs. Notice: you should copy the whole questions on your answer sheet.)
(106)
(a)
$$
A\to C, ((A\land B)\to C)\to D \vdash D
$$
答.
![[basic-logic/---attachments/logic-problem-6-2025-11-15-21-12-40.svg]]
(b)
$$
K \to \lnot L , M \to L \vdash K \to \lnot M
$$
答.
![[basic-logic/---attachments/logic-problem-6-2025-11-15-21-19-16.svg]]
(c)
$$
(\forall x)(\exists y)(Py \land Qxy) , (\exists x)\lnot Px \vdash (\exists y)(Py \land (\exists x)(\lnot Px \land Qxy))
$$
答.
$$
\array{
1. & (\forall x)(\exists y)(Py \land Qxy) & \text{Pr} \\
2. & (\exists x)\lnot Px & \text{Pr} \\
3. & \lnot Pa & \text{2, EI} \\
4. & (\exists y)(Py \land Qay) & \text{1, UI} \\
5. & Pb \land Qab & \text{4, EI} \\
6. & Qab & \text{5. Simp} \\
7. & \lnot Pa \land Qab & \text{3, 6, Conj} \\
8. & (\exists x) (\lnot Px \land Q xb) & 7, EG \\
9. & Pb & \text{5, Simp} \\
10. & Pb \land(\exists x)(\lnot Px \land Qxb) & \text{8, 9 , Conj} \\
11. & (\exists y)(Py \land (\exists x)(\lnot Px \land Qxy)) & \text{10, EG}
}
$$
---
六、請完成下列演算，作答時需連同題目寫在答案卷上。 (20%) Please complete the following calculations, and write the answer sheet together with the diagram.
(107)
(a) $$
\vdash \lnot (P \leftrightarrow \lnot P)
$$
答.
![[basic-logic/---attachments/logic-problem-6-2025-11-15-21-28-32.svg]]
(b)
$$\array{
(\forall x )(Lx \to (\exists y)(Ly \land Mxy)), (\exists x)(Lx \land (\forall y)((Ly \land Mxy)\to Nxy )) \\
\vdash (\exists x)(\exists y)((Lx \land Ly)\to Nxy)
}
$$
答.
$$
\array{
1. & (\forall x )(Lx \to (\exists y)(Ly \land Mxy)) & \text{Pr} \\
2. & (\exists x) (Lx \land (\forall y)((Ly\land Mxy)\to Nxy)) & \text{Pr} \\
3. & La \land (\forall y)((Ly\land May)\to Nay) & \text{2, EG} \\
4. & La & \text{3, Simp} \\
5. & La \to (\exists y)(Ly \land May) & \text{1, UI} \\
6. & (\exists y)(Ly \land May) & \text{4,5, MP} \\
7. & Lb \land Mab & \text{6, EI} \\
8. & (\forall y)((Ly \land May )\to Nay) & \text{3, Simp} \\
9. & (Lb \land Mab) \to Nab & \text{8, UI} \\
10. & Nab & \text{7,9, MP} \\
11. & Nab \lor \lnot La & \text{10, Add} \\
12. & (Nab \lor \lnot La) \lor \lnot Lb & \text{11, Add} \\
13. & Nab \lor (\lnot La \lor \lnot Lb) & \text{12, Asso} \\
14. & Nab \lor\lnot(La \land Lb) & \text{13, DeM} \\
15. & \lnot(La \land Lb) \lor Nab & \text{14, Comm} \\
16. & La \land Lb \to Nab & \text{15, Imp} \\
17. & (\exists y)((La \land Ly \to Nay)) & \text{16, EG} \\
18. & (\exists x)(\exists y)((Lx \land Ly) \to Nxy) & \text{17, EG}
}
$$
////